9033. Greedy Aziz

 

Do you know that Aziz loves chocolate sweets very much? However, his father does not allow him to eat a lot of chocolate because of his teeth.

Father gave him an array that contains a lot of identical numbers. During the day Aziz can eat as many candies as the maximum times the number in array is repeated.

Aziz wants to cheat to eat more candies. He can change some numbers in array, and the father will not notice it. He can increase or decrease any number in the array by 1 and only 1 time.

Aziz wants to eat the maximum number of sweets. Help him in this matter.

Find the maximum number of sweets Aziz can get.

 

Input. The first line contains the number of elements n (1 ≤ n ≤ 105) in array. The second line contains n elements ai (0 ≤ ai ≤ 109) of array.

 

Output. Print the maximum number of sweets Aziz can get.

 

Sample input 1

Sample output 1

2

1 2

2

 

 

Sample input 2

Sample output 2

4

1 3 3 5

3

 

 

SOLUTION

data structures map

 

Algorithm analysis

Count the number of times that each number occurs in the array. To do this, use the map data structure: m[x] will contain the number of times the number x occurs in the array.

For each number a[i] in the array, assume that it is the maximum occurring after Aziz’s fraud. To do this, Aziz must increase the number (a[i] – 1) by 1, and decrease the number (a[i] + 1) by 1 (if such numbers exist in array). For example, let the array look like

The map structure contains the following data (two fives, two sixes, and four sevens):

m[5] = 2, m[6] = 2, m[7] = 4

In order for the number 6 to be the most common after fraud, it is necessary to add 1 to all numbers 5, and subtract 1 from all numbers 7:

Let initially a[i] = 6. Then array initially contains m[a[i]] sixes, m[a[i] – 1] fives, and m[a[i] + 1] sevens. After cheating, the number of sixes will be

m[a[i] – 1] + m[a[i]] + m[a[i] + 1],

which will be the number of sweets that Aziz receive.

 

Consider the situation when the array contains two numbers a[i] = 4 and a[i] + 2 = 6 (the difference between which is 2), but the number a[i] + 1, for example, may be absent.

In this case, it would be optimal to increase all numbers a[i] by 1, and to decrease all numbers a[i] + 2 by 1. After the fraud, the amount of numbers a[i] + 1 will be

m[a[i]] + m[a[i] + 1] + m[a[i] + 2]

 

Algorithm realization

Declare the input array a. Declare a variable m of type map.

 

map<int, int> m;

int a[100000];

 

Read the input array. Count the number of times a[i] occurs in the array a.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

{

  scanf("%d", &a[i]);

  m[a[i]]++;

}

 

Compute the answer in the variable res.

 

int res = 0;

for (int i = 0; i < n; i++)

{

 

If the most frequently encountered number after cheating is a[i].

 

  res = max(res, m[a[i]] + m[a[i] - 1] + m[a[i] + 1]);

 

If the most frequently encountered number after cheating is a[i] + 1.

 

  res = max(res, m[a[i]] + m[a[i] + 1] + m[a[i] + 2]);

}

 

Print the answer.

 

printf("%d\n", res);

 

Java realization

 

import java.util.*;

 

public class Main

{

  static Map<Integer, Integer> m = new HashMap<Integer, Integer>();

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int a[] = new int[n];

    for (int i = 0; i < n; i++)

    {

      a[i] = con.nextInt();

      if (!m.containsKey(a[i]))

        m.put(a[i], 1);

      else

        m.put(a[i], m.get(a[i]) + 1);

    }

  

    int res = 0;

    for (int i = 0; i < n; i++)

    {

      int ai = 0;

      if (m.containsKey(a[i])) ai = m.get(a[i]);

      int aim1 = 0;

      if (m.containsKey(a[i]-1)) aim1 = m.get(a[i]-1);

      int aip1 = 0;

      if (m.containsKey(a[i]+1)) aip1 = m.get(a[i]+1);

      int aip2 = 0;

      if (m.containsKey(a[i]+2)) aip2 = m.get(a[i]+2);     

     

      res = Math.max(res, ai + aim1 + aip1);

      res = Math.max(res, ai + aip1 + aip2);

    }

   

    System.out.println(res);

    con.close();

  }

}